﻿using System;
using System.Collections.Generic;

class Labyrinth
{
    public const int LABYRINTH_SIZE = 7;
    private readonly int LabyrintStartRow = LABYRINTH_SIZE / 2;
    private readonly int LabyrinthStartCol = LABYRINTH_SIZE / 2;
    private Cell[,] gameBoard;
    public Cell CurrentCell { get; set; }

    public Labyrinth(Random rand)
    {
        GenerateLabyrinth(rand);
        CurrentCell = gameBoard[LabyrintStartRow, LabyrintStartRow];
    }

    public Cell GetCell(int row, int col)
    {
        return gameBoard[row, col];
    }

    public bool TryMove(Direction direction)
    {
        Cell nextCell = GetNextCell(CurrentCell, direction);
        if (nextCell == null || !nextCell.IsEmpty())
        {
            return false;
        }
        nextCell.Value = '*';
        CurrentCell.Value = '-';
        CurrentCell = nextCell;
        return true;
    }

    private Cell GetNextCell(Cell cell, Direction direction)
    {

        int newRow = cell.Row;
        int newCol = cell.Col;

        if (direction == Direction.Up)
        {
            newRow = newRow - 1;
        }
        else if (direction == Direction.Down)
        {
            newRow = newRow + 1;
        }
        else if (direction == Direction.Left)
        {
            newCol = newCol - 1;
        }
        else if (direction == Direction.Right)
        {
            newCol = newCol + 1;
        }

        Cell nextCell = null;
        if (AreCoordinatesValid(newRow, newCol))
        {
            nextCell = this.gameBoard[newRow, newCol];
        }
        return nextCell;
    }

    private bool AreCoordinatesValid(int newRow, int newCol)
    {
        if (newRow < 0 || newCol < 0 ||
                newRow >= gameBoard.GetLength(0) || newCol >= gameBoard.GetLength(1))
        {
            return false;
        }
        return true;
    }

    public bool ExitFound(Cell cell)
    {
        bool exitFound = false;
        bool isFirstOrLastRow = cell.Row == 0 || cell.Row == LABYRINTH_SIZE - 1;
        bool isFirstOrLastColumn = cell.Col == 0 || cell.Col == LABYRINTH_SIZE - 1;
        if (isFirstOrLastRow || isFirstOrLastColumn)
        {
            exitFound = true;
        }
        return exitFound;
    }

    public void Print()
    {
        int labyrinthSize = Labyrinth.LABYRINTH_SIZE;
        for (int row = 0; row < labyrinthSize; row++)
        {
            for (int col = 0; col < labyrinthSize; col++)
            {
                Cell cell = GetCell(row, col);
                Console.Write(cell.Value + " ");
            }
            Console.WriteLine();
        }
    }

    private bool HasPathToExit()
    {
        Queue<Cell> path = new Queue<Cell>();
        Cell startCell = gameBoard[LabyrintStartRow, LabyrinthStartCol];
        path.Enqueue(startCell);
        HashSet<Cell> visitedCells = new HashSet<Cell>();

        bool pathExists = false;
        while (path.Count > 0)
        {
            Cell currentCell = path.Dequeue();
            visitedCells.Add(currentCell);
            if (ExitFound(currentCell))
            {
                pathExists = true;
                break;
            }
            FindPathToExit(currentCell, Direction.Down, path, visitedCells);
            FindPathToExit(currentCell, Direction.Up, path, visitedCells);
            FindPathToExit(currentCell, Direction.Left, path, visitedCells);
            FindPathToExit(currentCell, Direction.Right, path, visitedCells);
        }
        return pathExists;
    }

    private void FindPathToExit(Cell cell, Direction direction,
    Queue<Cell> cellsOrder, HashSet<Cell> visitedCells)
    {
        Cell nextCell = GetNextCell(cell, direction);
        if (nextCell == null || visitedCells.Contains(nextCell))
        {
            return;
        }
        if (nextCell.IsEmpty())
        {
            cellsOrder.Enqueue(nextCell);
        }
    }

    private void GenerateLabyrinth(Random rand)
    {
        this.gameBoard = new Cell[LABYRINTH_SIZE, LABYRINTH_SIZE];

        for (int row = 0; row < LABYRINTH_SIZE; row++)
        {
            for (int col = 0; col < LABYRINTH_SIZE; col++)
            {
                int randomValueFromZeroToOne = rand.Next(0, 2);
                char charValue;
                if (randomValueFromZeroToOne == 0)
                {
                    charValue = Cell.CELL_EMPTY_VALUE;
                }
                else
                {
                    charValue = Cell.CELL_FULL_VALUE;
                }
                this.gameBoard[row, col] = new Cell(row, col, charValue);
            }
        }
        this.gameBoard[LabyrintStartRow, LabyrinthStartCol].Value = '*';
        bool exitPathExists = HasPathToExit();
        if (!exitPathExists)
        {
            GenerateLabyrinth(rand);
        }
    }
}

public enum Direction { Up, Down, Left, Right };
